#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <map>
#include <optional>
#include <queue>
#include <stack>
#include <stdexcept>
#include <string>
#include <vector>

#pragma once

using namespace std;

// ------------------- tools -------------------------
template <typename T>
T max(std::vector<T> vec) {
    if (vec.empty()) throw std::runtime_error("vec is empty");
    T tmp = vec[0];
    for (auto v : vec) {
        if (v > tmp) tmp = v;
    }
    return tmp;
}

template <typename T>
void print(std::vector<T> vec) {
    for (auto v : vec) {
        std::cout << v << ", ";
    }
    std::cout << '\n';
}

void print(bool flag) {
    if (flag)
        std::cout << "true" << std::endl;
    else
        std::cout << "false" << std::endl;
}

// --------------------- Binary_Tree ---------------
template <typename T>
class BTreeNode {
  public:
    BTreeNode(T value) : val{value}, right{nullptr}, left{nullptr} {}

    BTreeNode(std::vector<T> vec) {
        std::vector<BTreeNode<T> *> nodes;
        this->val = vec[0];
        nodes.push_back(this);
        for (int i = 1; i < vec.size(); ++i) {
            if (vec[i] != INT_MIN)
                nodes.push_back(new BTreeNode<T>(vec[i]));
            else
                nodes.push_back(nullptr);
        }
        for (int i = 0; i < vec.size() / 2; ++i) {
            if (i * 2 + 1 < vec.size()) nodes[i]->left = nodes[i * 2 + 1];
            if (i * 2 + 2 < vec.size()) nodes[i]->right = nodes[i * 2 + 2];
        }
    }

    ~BTreeNode() {
        if (right) delete right;
        if (left) delete left;
    }

    T val;
    BTreeNode *right;
    BTreeNode *left;
};

using TreeNode = BTreeNode<int>;

template <typename T>
void dfs_(BTreeNode<T> *root) {
    if (root->left) dfs_(root->left);
    if (root->right) dfs_(root->right);
    if (root) std::cout << root->val << ", ";
}

// -------------- List ---------------
template <typename T>
class OneWayListNode {
  public:
    T val;
    OneWayListNode *next;
    OneWayListNode(T x) : val(x), next(nullptr) {}

    ~OneWayListNode() {
        if (next) delete next;
    }
};

using ListNode = OneWayListNode<int>;

template <typename T>
OneWayListNode<T> *creat_list(std::vector<T> vec) {
    if (vec.empty()) return nullptr;
    OneWayListNode<T> *head = new OneWayListNode<T>(vec[0]);
    OneWayListNode<T> *tmp = head;
    for (int i = 1; i < vec.size(); ++i) {
        tmp->next = new OneWayListNode<T>(vec[i]);
        tmp = tmp->next;
    }
    return head;
}

template <typename T>
void print(OneWayListNode<T> *head) {
    auto tmp = head;
    while (tmp != nullptr) {
        std::cout << tmp->val << ", ";
        tmp = tmp->next;
    }
    std::cout << std::endl;
}

/*
template <typename T>
void dfs_fuck(BTreeNode<T> &root) {
    BTreeNode<T> *cur;
    cur = &root;
    std::stack<BTreeNode<T> *> nodes;
    while (not nodes.empty() or cur) {
        while (cur) {
            // front
            // std::cout << cur->val << ", ";
            nodes.push(cur);
            cur = cur->left;
        }
        if (not nodes.empty()) {
            // mid
            // std::cout << nodes.top()->val << ", ";
            cur = nodes.top()->right;
            nodes.pop();
        }
    }
}

// 后序可以用反转先右后左的先序遍历结果获得， 根右左 -> 左右根

template <typename T>
void dfs(BTreeNode<T> &root) {
    std::stack<BTreeNode<T> *> nodes;
    BTreeNode<T> *cur = &root;
    while (not nodes.empty() or cur) {
        if (cur) {
            // 先序
            std::cout << cur->val << ", ";
            nodes.push(cur);
            cur = cur->left;
        } else {
            if (nodes.top()->right) {
                cur = nodes.top()->right;
            }
            // 中序
            // std::cout << nodes.top()->val << ", ";
            nodes.pop();
        }
    }
    std::cout << '\n';
}

template <typename T>
void post_order_dfs(BTreeNode<T> *root) {
    if (not root) return;
    BTreeNode<T> *cur = nullptr;
    BTreeNode<T> *pre = nullptr;
    std::stack<BTreeNode<T> *> nodes;
    nodes.push(root);
    while (not nodes.empty()) {
        cur = nodes.top();
        if ((not cur->left and not cur->right) or (pre and (pre == cur->right or pre ==
cur->left))) { std::cout << cur->val << ", "; nodes.pop(); pre = cur; } else { if
(cur->right) nodes.push(cur->right); if (cur->left) nodes.push(cur->left);
        }
    }
}
*/
